#include <dbg.h>
#include <gtest/gtest.h>

#include <numeric>
using namespace std;

class Solution {
public:
    long long numberOfRightTriangles(vector<vector<int>>& grid) {
        int n = grid[0].size();

        // 行的元素个数
        vector<int> colCnt(n, -1);  // 提前减一，防止重复计算直角点
        for (const vector<int>& row : grid) {
            for (int i = 0; i < n; ++i) {
                colCnt[i] += row[i];
            }
        }
        dbg(colCnt);

        long long res = 0;
        // 列的元素个数
        for (const vector<int>& row : grid) {
            // 提前减一，防止重复计算直角点
            int rowCnt = reduce(row.begin(), row.end(), -1);
            dbg(rowCnt);
            for (int j = 0; j < n; ++j) {
                if (row[j] == 1) {
                    res += (rowCnt) * (colCnt[j]);
                }
            }
        }
        return res;
    }
};

TEST(TEST_numberoOfRightTriangles_Test1, numberOfRightTriangles) {
    Solution s;

    vector<vector<int>> grid = {{0, 1, 0}, {0, 1, 1}, {0, 1, 0}};
    EXPECT_EQ(s.numberOfRightTriangles(grid), 2);
}

TEST(TEST_numberoOfRightTriangles_Test2, numberOfRightTriangles) {
    Solution s;

    vector<vector<int>> grid = {{1, 0, 0, 0}, {0, 1, 0, 1}, {1, 0, 0, 0}};
    EXPECT_EQ(s.numberOfRightTriangles(grid), 0);
}

TEST(TEST_numberoOfRightTriangles_Test3, numberOfRightTriangles) {
    Solution s;

    vector<vector<int>> grid = {{1, 0, 1}, {1, 0, 0}, {1, 0, 0}};
    EXPECT_EQ(s.numberOfRightTriangles(grid), 2);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}